{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Splitting a String Into Descending Consecutive Values"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: splitString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将字符串拆分为递减的连续值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个仅由数字组成的字符串 <code>s</code> 。</p>\n",
    "\n",
    "<p>请你判断能否将 <code>s</code> 拆分成两个或者多个 <strong>非空子字符串</strong> ，使子字符串的 <strong>数值</strong> 按 <strong>降序</strong> 排列，且每两个 <strong>相邻子字符串</strong> 的数值之 <strong>差 </strong>等于 <code>1</code> 。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，字符串 <code>s = \"0090089\"</code> 可以拆分成 <code>[\"0090\", \"089\"]</code> ，数值为 <code>[90,89]</code> 。这些数值满足按降序排列，且相邻值相差 <code>1</code> ，这种拆分方法可行。</li>\n",
    "\t<li>另一个例子中，字符串 <code>s = \"001\"</code> 可以拆分成 <code>[\"0\", \"01\"]</code>、<code>[\"00\", \"1\"]</code> 或 <code>[\"0\", \"0\", \"1\"]</code> 。然而，所有这些拆分方法都不可行，因为对应数值分别是 <code>[0,1]</code>、<code>[0,1]</code> 和 <code>[0,0,1]</code> ，都不满足按降序排列的要求。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果可以按要求拆分 <code>s</code> ，返回 <code>true</code> ；否则，返回 <code>false</code><em> </em>。</p>\n",
    "\n",
    "<p><strong>子字符串</strong> 是字符串中的一个连续字符序列。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"1234\"\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>不存在拆分 s 的可行方法。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"050043\"\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>s 可以拆分为 [\"05\", \"004\", \"3\"] ，对应数值为 [5,4,3] 。\n",
    "满足按降序排列，且相邻值相差 <code>1</code> 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"9080701\"\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>不存在拆分 s 的可行方法。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"10009998\"\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>s 可以拆分为 [\"100\", \"099\", \"98\"] ，对应数值为 [100,99,98] 。\n",
    "满足按降序排列，且相邻值相差 <code>1</code> 。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= s.length <= 20</code></li>\n",
    "\t<li><code>s</code> 仅由数字组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [splitting-a-string-into-descending-consecutive-values](https://leetcode.cn/problems/splitting-a-string-into-descending-consecutive-values/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [splitting-a-string-into-descending-consecutive-values](https://leetcode.cn/problems/splitting-a-string-into-descending-consecutive-values/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"1234\"', '\"050043\"', '\"9080701\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def f(self, s, num):\n",
    "        if int(s)==num: return True\n",
    "        for i in range(1, len(s)):\n",
    "            if int(s[:i]) == num: return self.f(s[i:], num-1)\n",
    "        return False\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        return any(self.f(s[i:], int(s[:i])-1) for i in range(1, len(s)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        n, start, target = len(s), 0, {'0'}\n",
    "        for i in range(n - 1):\n",
    "            pre, cur, idx = (start := 10 * start + int(s[i])), 0, i + 1\n",
    "            for j in range(i + 1, n):\n",
    "                if pre == 1:\n",
    "                    if set(s[idx:n]) == target:\n",
    "                        return True\n",
    "                    else:\n",
    "                        break\n",
    "                if (cur := 10 * cur + int(s[j])) > pre - 1:\n",
    "                    break\n",
    "                elif cur == pre - 1:\n",
    "                    if j + 1 == n:\n",
    "                        return True\n",
    "                    pre, cur, idx = cur, 0, j + 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        start = 0\n",
    "        while start < n and s[start] == '0':\n",
    "            start += 1\n",
    "        \n",
    "        if start >= n - 1:\n",
    "            return False\n",
    "        \n",
    "        first = 0\n",
    "        for index in range(start, n - 1):\n",
    "            first = first * 10 + int(s[index])\n",
    "            last = first\n",
    "            p = index + 1\n",
    "            flag = True\n",
    "            while p < n:\n",
    "                if last == 0:\n",
    "                    while p < n and s[p] == '0':\n",
    "                        p += 1\n",
    "                    if p != n:\n",
    "                        flag = False\n",
    "                    break\n",
    "\n",
    "                now = int(s[p])\n",
    "                p += 1\n",
    "                while p < n and now < last - 1:\n",
    "                    now = now * 10 + int(s[p])\n",
    "                    p += 1\n",
    "\n",
    "                if now != last - 1:\n",
    "                    flag = False\n",
    "                    break\n",
    "                last = now\n",
    "\n",
    "            if flag:\n",
    "                return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        def dfs(idx, now):\n",
    "            if idx == n - 1:\n",
    "                return True\n",
    "            for i in range(idx + 1, n):\n",
    "                nxt = s[idx + 1: i + 1]\n",
    "                if int(nxt) == now - 1:\n",
    "                    if dfs(i, now - 1):\n",
    "                        return True\n",
    "            return False\n",
    "        for i in range(n - 1):\n",
    "            if dfs(i, int(s[:i + 1])):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        # 我自己写的有问题，下面是网友的写法\n",
    "        def dfs(elem,idx):\n",
    "            for i in range(idx,n):\n",
    "                if elem - int(s[idx:i + 1]) == 1:\n",
    "                    if i == n - 1 or (int(s[i]) == 0 and int(s[i:]) == 0):\n",
    "                        return True\n",
    "                    return dfs(elem - 1,i + 1)\n",
    "            return False\n",
    "\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            if dfs(int(s[:i +1]),i + 1):\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        # 方法2、带有剪枝的回溯\n",
    "        def backtrack(idx,path):\n",
    "            if idx == n and len(path) > 1:\n",
    "                return True\n",
    "            for i in range(idx,n):\n",
    "                num = int(s[idx:i + 1])\n",
    "                # 第一种情况是num恰好等于path的最后一个值，或者num就是第一个值，那么加入到path，然后递归进入下一层\n",
    "                if not path or path[-1] - num == 1:\n",
    "                    path.append(num)\n",
    "                    if backtrack(i + 1,path):\n",
    "                        return True\n",
    "                    path.pop()\n",
    "                # 第二种情况是num大于path的最后一个值，说明当前切分方式不对，应该回溯。\n",
    "                if path and num + 1 > path[-1]:\n",
    "                    return False\n",
    "                # 剩下一种情况是num小于path最后一个值，说明还需要再向右搜索下一个字符，使num变大\n",
    "            return False\n",
    "\n",
    "        n = len(s)\n",
    "        return backtrack(0,[])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "\n",
    "        def find(k,num,count):\n",
    "            if k==n:\n",
    "                if count>1:return True\n",
    "                return False\n",
    "            if num==0:\n",
    "                return int(s[k:])==0\n",
    "            t = ''\n",
    "            for i in range(k,n):\n",
    "                t +=s[i]\n",
    "                #print(t)\n",
    "                v= int(t)\n",
    "                if v == num:\n",
    "                    #print(v)\n",
    "                    return find(i+1,num-1,count+1)\n",
    "                if v>num:return False\n",
    "            return False\n",
    "\n",
    "        tmp = ''\n",
    "        for i in range(n):\n",
    "            tmp+=s[i]\n",
    "            if find(i+1,int(tmp)-1,1):\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        path = []\n",
    "        def dfs(k):\n",
    "            if k == n:\n",
    "                return len(path) >= 2 and path[-2] - path[-1] == 1\n",
    "            for i in range(k, n):\n",
    "                ss = int(s[k:i+1])\n",
    "                if (len(path) >= 1) and (path[-1] - ss != 1):\n",
    "                    if ss >= path[-1]:\n",
    "                        return False\n",
    "                    else:\n",
    "                        continue\n",
    "                path.append(ss)\n",
    "                if dfs(i + 1):\n",
    "                    return True\n",
    "                path.pop()\n",
    "            return False\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        \n",
    "        def dfs(head, s: str):\n",
    "            # 能否拆分成以head开头的递减的数列\n",
    "            if head == \"0\":\n",
    "                return int(s) == 0\n",
    "            s = s.lstrip(\"0\")\n",
    "            if not s.startswith(head):\n",
    "                return False\n",
    "            if head == s:\n",
    "                return True\n",
    "            return dfs(str(int(head) - 1), s.replace(head, \"\", 1))\n",
    "\n",
    "        for i in range(1, len(s)):\n",
    "            val = s[:i]\n",
    "            if dfs(str(int(val) - 1), s[i:]):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        def dfs(pos, pre_num):\n",
    "            if pos == n: \n",
    "                return True\n",
    "            for i in range(pos, n):\n",
    "                cur_num = int(s[pos:i+1])\n",
    "                if cur_num +1 == pre_num:\n",
    "                    if dfs(i+1, cur_num): return True\n",
    "                if cur_num > pre_num:\n",
    "                    return False\n",
    "            return False\n",
    "        \n",
    "        n = len(s)\n",
    "        for i in range(1, n):\n",
    "            if dfs(i, int(s[:i])): return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        path = []\n",
    "        def dfs(k):\n",
    "            if k == n:\n",
    "                return len(path) >= 2\n",
    "            for i in range(k, n):\n",
    "                ss = s[k:i+1]\n",
    "                if (len(path) >= 1) and (path[-1] - int(ss) != 1):\n",
    "                    if int(ss) >= path[-1]:\n",
    "                        return False\n",
    "                    else:\n",
    "                        continue\n",
    "                path.append(int(ss))\n",
    "                if dfs(i + 1):\n",
    "                    return True\n",
    "                path.pop()\n",
    "            return False\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        a = int(s)\n",
    "        def backtrack(index,pre):\n",
    "            if index >= len(s) and pre != a:\n",
    "                return True \n",
    "            for i in range(index,len(s)):\n",
    "                num = int(s[index:i+1])\n",
    "                if pre == '*' or pre - num == 1:\n",
    "                    if backtrack(i+1,num):\n",
    "                        return True \n",
    "            return False\n",
    "        return backtrack(0,'*')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        n=len(s)\n",
    "        def f(pre,p):\n",
    "            if p==n-1:\n",
    "                return True\n",
    "            for i in range(p+1,n):\n",
    "                if int(s[p+1:i+1])==pre-1 and (i+1==n or int(s[p+1:i+2])!=pre-1):\n",
    "                    if f(pre-1,i):\n",
    "                        return True \n",
    "            return False\n",
    "        for i in range(1,n):\n",
    "            if f(int(s[:i]),i-1):\n",
    "                return True \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def dfs(left, right, pre):  # 返回在s[left:right + 1]之后切一刀能否满足条件\n",
    "            x = int(s[left:right + 1])\n",
    "            if (x == pre - 1 and right == n - 1):\n",
    "                return True\n",
    "            if pre != -1 and x != pre - 1:\n",
    "                return False\n",
    "            for i in range(right + 1, n):\n",
    "                if dfs(right + 1, i, x):\n",
    "                    return True\n",
    "            return False\n",
    "        for i in range(n):\n",
    "            if dfs(0, i, -1):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        def dfs(left, right):  # 返回在s[left:right + 1]之后切一刀能否满足条件\n",
    "            if right == n - 1:\n",
    "                return True\n",
    "            x = int(s[left:right + 1])\n",
    "            for i in range(right + 1, n):\n",
    "                if int(s[right + 1:i + 1]) == x - 1:\n",
    "                    if dfs(right + 1, i):\n",
    "                        return True\n",
    "            return False\n",
    "        for i in range(n - 1):\n",
    "            if dfs(0, i):\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "      def dfs(s, temp):\n",
    "        if not s and len(temp) >= 2:\n",
    "          res.append(temp)\n",
    "        for i in range(len(s)):\n",
    "          cur = s[:i+1]\n",
    "          if not temp or int(cur) == (temp[-1]-1):\n",
    "            print(s, temp)\n",
    "            dfs(s[i+1:],  temp+[int(cur)])\n",
    "      res = []\n",
    "      dfs(s, [])\n",
    "      # print(res)\n",
    "      return True if res else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 深度优先搜索+回溯\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        n=len(s)\n",
    "        def dfs(cur,path):\n",
    "            if cur==n and len(path)>1:\n",
    "                return True\n",
    "\n",
    "            for i in range(cur,n):\n",
    "                num=int(s[cur:i+1])\n",
    "                # 第一种情况是num恰好等于path的最后一个值，或者num就是第一个值，那么加入到path，然后递归进入下一层\n",
    "                if not path or num==path[-1]-1:\n",
    "                    path.append(num)\n",
    "                    if dfs(i+1, path):\n",
    "                        return True\n",
    "\n",
    "                    path.pop()\n",
    "\n",
    "                # 第二种情况是num大于path的最后一个值，说明当前切分方式不对，应该回溯。\n",
    "                if path and num>path[-1]-1:\n",
    "                    return False\n",
    "\n",
    "                # 剩下一种情况是num小于path最后一个值，说明还需要再向右搜索下一个字符，使num变大\n",
    "\n",
    "            return False\n",
    "\n",
    "        return dfs(0,[])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "\n",
    "        # 清风python\n",
    "        # n = len(s)\n",
    "        # def dfs(num, idx):\n",
    "        #     for i in range(idx, n):  # 从当前分割点往后遍历\n",
    "        #         if int(s[idx:i+1]) == num-1:\n",
    "        #             if i==n-1 or (int(s[i])==0 and int(s[i:])==0):\n",
    "        #                 return True\n",
    "        #             return dfs(num-1, i+1)\n",
    "        #     return False\n",
    "        \n",
    "        # for i in range(n):\n",
    "        #     if dfs(int(s[:i+1]), i+1):\n",
    "        #         return True\n",
    "        # return False\n",
    "\n",
    "\n",
    "\n",
    "        # 网友\n",
    "        n = len(s)\n",
    "        def back_tracking(idx, prev_num):\n",
    "            nonlocal n\n",
    "            if idx == n:\n",
    "                return True\n",
    "            for i in range(1, n - idx + 1):\n",
    "                num = int(s[idx: idx + i])\n",
    "                if num + 1 == prev_num and back_tracking(idx + i, num):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        for i in range(1, n):\n",
    "            first_num = int(s[:i])\n",
    "            if back_tracking(i, first_num):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        s_num = []\n",
    "        def backtracking(split_idx: int):\n",
    "            print(\"checked \", s_num)\n",
    "            if not s_num:\n",
    "                num_last = None\n",
    "            else:\n",
    "                num_last = int(s_num[-1])\n",
    "            if split_idx > len(s) - 1:\n",
    "                return len(s_num) > 1\n",
    "            for split_idx_ in range(split_idx, len(s)):\n",
    "                new_string = s[split_idx:split_idx_ + 1]\n",
    "                print(new_string)\n",
    "                num_current = int(new_string)\n",
    "                if num_last is not None and num_last - num_current != 1:\n",
    "                    if num_current == 0 or num_current < num_last:\n",
    "                        continue\n",
    "                    else:\n",
    "                        break\n",
    "                s_num.append(new_string)\n",
    "                found = backtracking(split_idx_ + 1)\n",
    "                if found:\n",
    "                    return True\n",
    "                s_num.pop()\n",
    "            return False\n",
    "        return backtracking(0)\n",
    "               \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "\n",
    "        def dfs(num, idx):\n",
    "            for i in range(idx, n):  # 从当前分割点往后遍历\n",
    "                if int(s[idx:i+1]) == num-1:\n",
    "                    if i==n-1 or (int(s[i])==0 and int(s[i:])==0):\n",
    "                        return True\n",
    "                    return dfs(num-1, i+1)\n",
    "            return False\n",
    "        \n",
    "        for i in range(n):\n",
    "            if dfs(int(s[:i+1]), i+1):\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        res = False\n",
    "        def dfs(s,pre,cur,pre_num):\n",
    "            nonlocal res\n",
    "            cur_num = int(s[pre+1:cur+1])\n",
    "            if cur_num == pre_num-1 or pre == -1:\n",
    "                if cur == len(s)-1:\n",
    "                    res = True\n",
    "                    return\n",
    "                for i in range(cur+1,len(s)):\n",
    "                    dfs(s,cur,i,cur_num)\n",
    "        for i in range(len(s)-1):\n",
    "            dfs(s,-1,i,0)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def splitString(self, s: str) -> bool:\r\n",
    "\r\n",
    "        def dfs(i: int, pre: int, pre_num: int, cnt: int) -> bool:\r\n",
    "            if i == len(s):\r\n",
    "                if pre == len(s) and cnt > 1:\r\n",
    "                    return True\r\n",
    "                return False\r\n",
    "            res = False\r\n",
    "            res = res or dfs(i + 1, pre, pre_num, cnt)\r\n",
    "            if pre_num == inf or int(s[pre:i + 1]) + 1 == pre_num:\r\n",
    "                res = res or dfs(i + 1, i + 1, int(s[pre:i + 1]), cnt + 1)\r\n",
    "            return res \r\n",
    "        return dfs(0, 0, inf, 0)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        p = [range(10**21)]  # 全集\n",
    "        for n in range(1, len(s)+1):\n",
    "            p.append(set())\n",
    "            for i in range(0, n):\n",
    "                nv = int(s[i:n])\n",
    "                if nv+1 in p[i]:\n",
    "                    p[n].add(nv)\n",
    "        return len(p[len(s)]) > 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "\n",
    "        def find_match(mother: str, son: str):  # mother 是不是 son 开头，并且之后还有内容\n",
    "            if mother == \"\":\n",
    "                return False\n",
    "            begin = 0\n",
    "            while begin < len(mother) and mother[begin] == '0':\n",
    "                begin += 1\n",
    "                pass\n",
    "            if begin == len(mother):\n",
    "                return int(son) == 0\n",
    "                pass\n",
    "            true_mother = mother[begin:]\n",
    "            if true_mother.startswith(son):\n",
    "                if len(true_mother) == len(son):\n",
    "                    return True\n",
    "                else:\n",
    "                    return find_match(true_mother[len(son):], str(int(son) - 1))\n",
    "                pass\n",
    "            else:\n",
    "                return False\n",
    "            pass\n",
    "\n",
    "        # 首先去掉首部的空格\n",
    "        begin = 0\n",
    "        while begin < len(s) and s[begin] == '0':\n",
    "            begin += 1\n",
    "            pass\n",
    "\n",
    "        # 特殊情况，如果有效长度过短，那么是无法支撑进行下一步的\n",
    "        if n - begin < 2:\n",
    "            return False\n",
    "\n",
    "        for right in range(begin + 1, int((n + begin + 1) / 2 + 1)):\n",
    "            ss = s[begin: right]\n",
    "            if find_match(s[right:], str(int(ss) - 1)):\n",
    "                return True\n",
    "\n",
    "        return False\n",
    "\n",
    "    pass\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def dfs(left, right, pre):  # 返回在s[left:right + 1]之后切一刀能否满足条件\n",
    "            x = int(s[left:right + 1])\n",
    "            if (x == pre - 1 and right == n - 1):\n",
    "                return True\n",
    "            if pre != -1 and x != pre - 1:\n",
    "                return False\n",
    "            for i in range(right + 1, n):\n",
    "                if dfs(right + 1, i, x):\n",
    "                    return True\n",
    "            return False\n",
    "        for i in range(n):\n",
    "            if dfs(0, i, -1):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def dfs(left, right):  # 返回在s[left:right + 1]之后切一刀能否满足条件\n",
    "            if right == n - 1:\n",
    "                return True\n",
    "            x = int(s[left:right + 1])\n",
    "            for i in range(right + 1, n):\n",
    "                if int(s[right + 1:i + 1]) == x - 1:\n",
    "                    if dfs(right + 1, i):\n",
    "                        return True\n",
    "            return False\n",
    "        for i in range(n - 1):\n",
    "            if dfs(0, i):\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "\n",
    "        def dfs(i, pre=None):\n",
    "            # print(i, pre)\n",
    "            if i == n:\n",
    "                if pre != int(s):\n",
    "                    return True\n",
    "                return False\n",
    "            if pre is None:\n",
    "                for j in range(i, n):\n",
    "                    num = int(s[i:j+1])\n",
    "                    if num == 0:\n",
    "                        continue\n",
    "                    if dfs(j+1, num):\n",
    "                        return True\n",
    "            else:\n",
    "                for j in range(i, n):\n",
    "                    num = int(s[i:j+1])\n",
    "                    if num == pre - 1:\n",
    "                        if dfs(j+1, num):\n",
    "                            return True\n",
    "            return False\n",
    "\n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        def take(x:int, s:str) -> bool:\n",
    "            if not s:\n",
    "                return True\n",
    "            for i in range(1,len(s)+1):\n",
    "                if int(s[:i]) == x and take(x-1, s[i:]):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        for i in range(1,len(s)):\n",
    "            if take(int(s[:i])-1, s[i:]):\n",
    "                return True\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def dfs(left, right, pre):  # 返回在s[left:right + 1]之后切一刀能否满足条件\n",
    "            x = int(s[left:right + 1])\n",
    "            if (x == pre - 1 and right == n - 1):\n",
    "                return True\n",
    "            if pre != -1 and x != pre - 1:\n",
    "                return False\n",
    "            for i in range(right + 1, n):\n",
    "                if dfs(right + 1, i, x):\n",
    "                    return True\n",
    "            return False\n",
    "        for i in range(n):\n",
    "            if dfs(0, i, -1):\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def splitString(self, s: str) -> bool:\r\n",
    "\r\n",
    "        def dfs(i: int, pre: int, pre_num: int, cnt: int) -> bool:\r\n",
    "            if i == len(s):\r\n",
    "                if pre == len(s) and cnt > 1:\r\n",
    "                    return True\r\n",
    "                return False\r\n",
    "            return dfs(i + 1, pre, pre_num, cnt) or (pre_num == inf or int(s[pre:i + 1]) + 1 == pre_num) and dfs(i + 1, i + 1, int(s[pre:i + 1]), cnt + 1)\r\n",
    "        return dfs(0, 0, inf, 0)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def dfs(i, pre):\n",
    "            if i == n:\n",
    "                return pre != int(s)\n",
    "            for j in range(i, n):\n",
    "                cur = int(s[i:j+1])\n",
    "                if pre == -1 or cur + 1 == pre:\n",
    "                    if dfs(j + 1, cur):\n",
    "                        return True\n",
    "            return False\n",
    "        return dfs(0, -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, prev_val, s, idx):\n",
    "        n = len(s)\n",
    "        if idx == n:\n",
    "            return True\n",
    "        \n",
    "        for i in range(idx + 1, n + 1):\n",
    "            next_val = int(s[idx:i])\n",
    "            if next_val == 0 and i < n:\n",
    "                continue\n",
    "            if next_val == prev_val - 1:\n",
    "                if self.dfs(next_val, s, i):\n",
    "                    return True\n",
    "        return False\n",
    "    \n",
    "    def splitString(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        for i in range(1, n):\n",
    "            val = int(s[:i])\n",
    "            if val == 0:\n",
    "                continue\n",
    "            if self.dfs(val, s, i):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 深度优先搜索+回溯+剪枝\n",
    "    def splitString(self, s: str) -> bool:\n",
    "\n",
    "        def dfs(pre, i):\n",
    "            nonlocal ans\n",
    "            # 剪枝\n",
    "            if ans or (len(lst) >= 2 and lst[-1] != lst[-2] - 1):\n",
    "                return\n",
    "            \n",
    "            if i == n:\n",
    "                if pre:\n",
    "                    lst.append(int(pre))\n",
    "                    \n",
    "                # 判断结果\n",
    "                if len(lst) >= 2 and lst[-1] == lst[-2] - 1:\n",
    "                    ans = True\n",
    "\n",
    "                if pre:\n",
    "                    lst.pop()\n",
    "\n",
    "                return\n",
    "            \n",
    "            if pre:\n",
    "                # 回溯\n",
    "                lst.append(int(pre))\n",
    "                dfs(s[i], i+1)\n",
    "                lst.pop()\n",
    "\n",
    "            dfs(pre+s[i], i+1)\n",
    "            return\n",
    "\n",
    "\n",
    "        n = len(s)\n",
    "        ans = False\n",
    "        lst = []\n",
    "        # 深搜\n",
    "        dfs(\"\", 0)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 深度优先搜索+回溯\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        def dfs(cur, path):\n",
    "            if cur == n and len(path)>1:\n",
    "                return True\n",
    "\n",
    "            for i in range(cur, n):\n",
    "                num=int(s[cur:i + 1])\n",
    "                # 第一种情况是num恰好等于path的最后一个值，或者num就是第一个值，那么加入到path，然后递归进入下一层\n",
    "                if not path or num==path[-1] - 1:\n",
    "                    path.append(num)\n",
    "                    if dfs(i + 1, path):\n",
    "                        return True\n",
    "\n",
    "                    path.pop()\n",
    "\n",
    "                # 第二种情况是num大于path的最后一个值，说明当前切分方式不对，应该回溯。\n",
    "                if path and num > path[-1] - 1:\n",
    "                    return False\n",
    "\n",
    "                # 剩下一种情况是num小于path最后一个值，说明还需要再向右搜索下一个字符，使num变大\n",
    "\n",
    "            return False\n",
    "\n",
    "        return dfs(0,[])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        def dfs(n1, r):\n",
    "            if not r:\n",
    "                return True\n",
    "            if int(r) - int(n1) == -1:\n",
    "                return True\n",
    "            elif int(r) - int(n1) < -1:\n",
    "                return False\n",
    "            else:\n",
    "                for i in range(1,len(r)):\n",
    "                    if int(n1) - int(r[:i]) == 1:\n",
    "                        print(\"heu\",i,r[:i])\n",
    "                        if dfs(r[:i], r[i:]):\n",
    "                            return True\n",
    "        l = len(s)\n",
    "        for i in range(1,l):\n",
    "            n1, r = s[:i], s[i:]\n",
    "            print(n1,r)\n",
    "            if dfs(n1,r):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            pval = int(s[0:(i+1)])\n",
    "            start = i+1\n",
    "            for j in range(start, len(s)):\n",
    "                if pval == 1: ##特判结尾0\n",
    "                    if int(s[start:]) == 0:\n",
    "                        return True \n",
    "                    else:\n",
    "                        break\n",
    "                cval = int(s[start:(j+1)])\n",
    "                print(cval, pval)\n",
    "                if cval == pval - 1:\n",
    "                    if j == len(s)-1:\n",
    "                        return True\n",
    "                    pval = cval \n",
    "                    start = j + 1\n",
    "        \n",
    "        return False\n",
    "                    \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        n=len(s)\n",
    "        def dfs(cur,path):\n",
    "            if cur==n and len(path)>1:\n",
    "                return True\n",
    "            for i in range(cur,n):\n",
    "                num=int(s[cur:i+1])\n",
    "                # 第一种情况是num恰好等于path的最后一个值，或者num就是第一个值，那么加入到path，然后递归进入下一层\n",
    "                if not path or num==path[-1]-1:\n",
    "                    path.append(num)\n",
    "                    if dfs(i+1, path):\n",
    "                        return True\n",
    "                    path.pop()\n",
    "                # 第二种情况是num大于path的最后一个值，说明当前切分方式不对，应该回溯。\n",
    "                if path and num>path[-1]-1:\n",
    "                    return False\n",
    "                # 剩下一种情况是num小于path最后一个值，说明还需要再向右搜索下一个字符，使num变大\n",
    "            return False\n",
    "        return dfs(0,[])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 深度优先搜索+回溯+剪枝\n",
    "    def splitString(self, s: str) -> bool:\n",
    "\n",
    "        def dfs(pre, i):\n",
    "            nonlocal ans\n",
    "            # 剪枝\n",
    "            if ans or (len(lst) >= 2 and lst[-1] != lst[-2] - 1):\n",
    "                return\n",
    "            \n",
    "            if i == n:\n",
    "                if pre:\n",
    "                    lst.append(int(pre))\n",
    "                    \n",
    "                # 判断结果\n",
    "                if len(lst) >= 2 and lst[-1] == lst[-2] - 1:\n",
    "                    ans = True\n",
    "\n",
    "                if pre:\n",
    "                    lst.pop()\n",
    "\n",
    "                return\n",
    "            \n",
    "            if pre:\n",
    "                # 回溯\n",
    "                lst.append(int(pre))\n",
    "                dfs(s[i], i+1)\n",
    "                lst.pop()\n",
    "\n",
    "            dfs(pre+s[i], i+1)\n",
    "            return\n",
    "\n",
    "\n",
    "        n = len(s)\n",
    "        ans = False\n",
    "        lst = []\n",
    "        # 深搜\n",
    "        dfs(\"\", 0)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitString(self, s: str) -> bool:\n",
    "        #关于字符拆分的，递归的输入输出可以按照上个字符和剩余的字符进行\n",
    "        def dfs(n1, r):\n",
    "            if not r:\n",
    "                return True\n",
    "            if int(r) - int(n1) == -1:\n",
    "                return True\n",
    "            elif int(r) - int(n1) < -1:\n",
    "                return False\n",
    "            else:\n",
    "                for i in range(1,len(r)):\n",
    "                    if int(n1) - int(r[:i]) == 1:\n",
    "                        #print(\"heu\",i,r[:i])\n",
    "                        if dfs(r[:i], r[i:]):\n",
    "                            return True\n",
    "        l = len(s)\n",
    "        for i in range(1,l):\n",
    "            n1, r = s[:i], s[i:]\n",
    "            print(n1,r)\n",
    "            if dfs(n1,r):\n",
    "                return True\n",
    "        return False"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
